LASeR is a multimedia content format defined to provide simple multimedia services to resource-limited devices such as mobile phones. LASeR can be used for applications such as map applications, animation, and 2-dimensional vector graphics. Such applications work with a large amount of point data, so a method for efficiently encoding point data is required. To this end, two major factors of LASeR should be considered: an efficient binary representation and a small decoder memory.
LASeR Text of the International Standardization Organization/International Electrotechnical Commission (ISO/IEC) 14496-20 Committee Draft (CD) published on July 2004 proposes a fixed length (FL) encoding scheme to encode LASeR point data. According to the FL encoding scheme, point data itself is encoded when a number of points, nbPoint, is less than three. When the number, nbPoint, is three or more, all point sequences are examined to determine a dynamic range of them and point sequences are encoded using a fixed length derived from the examination result. The method can be implemented very simply. However, not only is there an overhead of ten bits in order to designate a length field on each point sequence, but there are also many bits unnecessarily allocated to a data field following the length field.
Entropy encoding and decoding may be considered to efficiently compress and restore image data. Entropy encoding is a method that considers various values which data can take and encodes the frequently-taken values using a small number of bits.
There are various entropy encoding schemes, which can be roughly classified into ones with an encoding table and ones without an encoding table. Huffman encoding scheme is a representative scheme using an encoding table. According to Huffman encoding scheme, a most optimized compression rate can be obtained. However, an encoding table must be transmitted, and there is a process overhead in a decoder (terminal) in that it has to access a memory location every time point data is decoded. Since the LASeR needs a small memory with minimal complexity, Huffman encoding scheme using an encoding table is not appropriate for encoding point data.
As other entropy encoding scheme, i.e., the encoding schemes not using an encoding table, there are arithmetic encoding and exponential golomb (EG) encoding schemes. Arithmetic encoding is an efficient encoding method but hard to use for LASeR due to the lack of error resilience.
On the other hand, the EG encoding scheme has some characteristics appropriate for LASeR. According to EG encoding scheme, a parameter k, which gives a low overhead to an encoder and is appropriate for a specific distribution, may be selected. In addition, the EG encoding can be easily converted into variable-length coding (VLC), in order to add an error resilient function (refer to “Reversible VLC for Added Error Resilience” by ISO/IEC Joint Technical Committee (JTC) 1/Section Committee (SC) 29/Working Group (WG) 1 (International Telecommunication Union-Telecommunication Standardization Section, Study Group 8 (ITU-T SG8)). Yet another advantage is a low decoder overhead. Since a decoding process can be performed by only addition and bit shift operations, the EG encoding scheme can be applied to low-end devices such as mobile phones without incurring a high overhead.